<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
   <head>
		<meta http-equiv="content-type" content="text/html;charset=ISO-8859-1">
	   <link href="/svn_public/templates/BlueGrey/styles.css" rel="stylesheet" media="screen">
      <!--[if gte IE 5.5000]>
      <script type="text/javascript" src="/svn_public/templates/BlueGrey/png.js"></script>
      <![endif]-->
      <title>
         WebSVN
            - dollar_recognizer
               - Rev 2
            - /dollar.py
      </title>

      <script>
         function checkCB(chBox)
         {
            count = 0
            first = null
            f = chBox.form
            for (i = 0 ; i < f.elements.length ; i++)
            if (f.elements[i].type == 'checkbox' && f.elements[i].checked)
            {
               if (first == null && f.elements[i] != chBox)
                  first = f.elements[i]
               count += 1
            }
            
            if (count > 2) 
            {
               first.checked = false
               count -= 1
            }
         }
      </script>

   </head>
   <body>

      <div style="text-align: center">
        <a href="http://subversion.tigris.org/"><img style="border: 0; width: 468px; height: 64px" src="/svn_public/templates/BlueGrey/subversion.png" alt="Subversion" /></a>
      </div>
      
      <hr>

<div align="right"><form action="/svn_public/wsvn" method="post" name="projectform"><select name="repname" onchange="javascript:this.form.submit();"><option value="dcuttxml" >dcuttxml</option><option value="dollar_recognizer" selected>dollar_recognizer</option><option value="freespace" >freespace</option><option value="idlers-irssi" >idlers-irssi</option><option value="twitter-irssi" >twitter-irssi</option></select><input type="submit" value="Go"><input type="hidden" name="selectproj" value="1"><input type="hidden" name="op" value="form"><input type="hidden" name="sc" value="0"></form></div>
<h2>dollar_recognizer</h2>
[<a href="/svn_public/wsvn/dollar_recognizer/?rev=0&amp;sc=0">/]</a> [<b>dollar.py</b>] - Rev 2
<p>
<a href="/svn_public/wsvn/dollar_recognizer/dollar.py?op=diff&amp;rev=0&amp;sc=0">Compare with Previous</a> - <a href="/svn_public/wsvn/dollar_recognizer/dollar.py?op=blame&amp;rev=0&amp;sc=0">Blame</a>
<p>
<hr>
<table width="100%" border=0><tr><td class="row0">
<PRE>
<I><FONT COLOR="#B22222">#
</FONT></I><I><FONT COLOR="#B22222">#  The $1 Gesture Recognizer
</FONT></I><I><FONT COLOR="#B22222">#
</FONT></I><I><FONT COLOR="#B22222">#      Jacob O. Wobbrock
</FONT></I><I><FONT COLOR="#B22222">#      The Information School
</FONT></I><I><FONT COLOR="#B22222">#      University of Washington
</FONT></I><I><FONT COLOR="#B22222">#      Mary Gates Hall, Box 352840
</FONT></I><I><FONT COLOR="#B22222">#      Seattle, WA 98195-2840
</FONT></I><I><FONT COLOR="#B22222">#      wobbrock@u.washington.edu
</FONT></I><I><FONT COLOR="#B22222">#
</FONT></I><I><FONT COLOR="#B22222">#      Andrew D. Wilson
</FONT></I><I><FONT COLOR="#B22222">#      Microsoft Research
</FONT></I><I><FONT COLOR="#B22222">#      One Microsoft Way
</FONT></I><I><FONT COLOR="#B22222">#      Redmond, WA 98052
</FONT></I><I><FONT COLOR="#B22222">#      awilson@microsoft.com
</FONT></I><I><FONT COLOR="#B22222">#
</FONT></I><I><FONT COLOR="#B22222">#      Yang Li
</FONT></I><I><FONT COLOR="#B22222">#      Department of Computer Science and Engineering
</FONT></I><I><FONT COLOR="#B22222">#      University of Washington
</FONT></I><I><FONT COLOR="#B22222">#      The Allen Center, Box 352350
</FONT></I><I><FONT COLOR="#B22222">#      Seattle, WA 98195-2840
</FONT></I><I><FONT COLOR="#B22222">#      yangli@cs.washington.edu
</FONT></I><I><FONT COLOR="#B22222">#
</FONT></I><I><FONT COLOR="#B22222"># Python port:
</FONT></I><I><FONT COLOR="#B22222"># Charlie Von Metzradt, November 2008
</FONT></I><I><FONT COLOR="#B22222"># http://sleepygeek.org
</FONT></I><I><FONT COLOR="#B22222">#
</FONT></I><I><FONT COLOR="#B22222"># Usage example:
</FONT></I><I><FONT COLOR="#B22222">#
</FONT></I><I><FONT COLOR="#B22222"># from dollar import Recognizer
</FONT></I><I><FONT COLOR="#B22222">#
</FONT></I><I><FONT COLOR="#B22222"># r = Recognizer()
</FONT></I><I><FONT COLOR="#B22222"># r.addTemplate('square', [(1, 10), (3, 8) ... ])
</FONT></I><I><FONT COLOR="#B22222"># r.addTemplate('circle', [(4, 7), (5, 13) ... ])
</FONT></I><I><FONT COLOR="#B22222">#
</FONT></I><I><FONT COLOR="#B22222"># (name, score) = r.recognize([(5, 6), (7, 12), ... ])
</FONT></I><I><FONT COLOR="#B22222">#
</FONT></I>
<B><FONT COLOR="#A020F0">import</FONT></B> math

<I><FONT COLOR="#B22222"># Contants. Tweak at your peril. :)
</FONT></I>
numPoints      = 64
squareSize     = 250.0
halfDiagonal   = 0.5 * math.sqrt(250.0 * 250.0 + 250.0 * 250.0)
angleRange     = 45.0
anglePrecision = 2.0
phi            = 0.5 * (-1.0 + math.sqrt(5.0)) <I><FONT COLOR="#B22222"># Golden Ratio
</FONT></I> 
<B><FONT COLOR="#A020F0">class</FONT></B> Recognizer:
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#BC8F8F">&quot;&quot;&quot;The $1 gesture recognizer. See http://sleepygeek.org/projects.dollar for more, or http://depts.washington.edu/aimgroup/proj/dollar/ for the original implementation and paper.&quot;&quot;&quot;</FONT></B>
&nbsp;&nbsp;&nbsp;templates = []

&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">def</FONT></B> <B><FONT COLOR="#0000FF">recognize</FONT></B>(self, points):
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#BC8F8F">&quot;&quot;&quot;Determine which gesture template most closely matches the gesture represented by the input points. 'points' is a list of tuples, eg: [(1, 10), (3, 8) ...]. Returns a tuple of the form (name, score) where name is the matching template, and score is a float [0..1] representing the match certainty.&quot;&quot;&quot;</FONT></B>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;points = [Point(point[0], point[1]) <B><FONT COLOR="#A020F0">for</FONT></B> point <B><FONT COLOR="#A020F0">in</FONT></B> points]
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;points = _resample(points, numPoints);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;points = _rotateToZero(points);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;points = _scaleToSquare(points, squareSize);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;points = _translateToOrigin(points);
&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bestDistance = float(<B><FONT COLOR="#BC8F8F">&quot;infinity&quot;</FONT></B>)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bestTemplate = None
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">for</FONT></B> template <B><FONT COLOR="#A020F0">in</FONT></B> self.templates:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;distance = _distanceAtBestAngle(points, template, -angleRange, +angleRange, anglePrecision)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">if</FONT></B> distance &lt; bestDistance:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bestDistance = distance
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bestTemplate = template

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;score = 1.0 - (bestDistance / halfDiagonal)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">return</FONT></B> (bestTemplate.name, score)

&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">def</FONT></B> <B><FONT COLOR="#0000FF">addTemplate</FONT></B>(self, name, points):
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#BC8F8F">&quot;&quot;&quot;Add a new template, and assign it a name. Multiple templates can be given the same name, for more accurate matching. Returns an integer representing the number of templates matching this name.&quot;&quot;&quot;</FONT></B>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.templates.append(Template(name, points))
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<I><FONT COLOR="#B22222"># Return the number of templates with this name.
</FONT></I>      <B><FONT COLOR="#A020F0">return</FONT></B> len([t <B><FONT COLOR="#A020F0">for</FONT></B> t <B><FONT COLOR="#A020F0">in</FONT></B> self.templates <B><FONT COLOR="#A020F0">if</FONT></B> t.name == name])      

&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">def</FONT></B> <B><FONT COLOR="#0000FF">deleteTemplates</FONT></B>(self, name):
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#BC8F8F">&quot;&quot;&quot;Remove all templates matching a given name. Returns an integer representing the new number of templates.&quot;&quot;&quot;</FONT></B>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.templates = [t <B><FONT COLOR="#A020F0">for</FONT></B> t <B><FONT COLOR="#A020F0">in</FONT></B> self.templates <B><FONT COLOR="#A020F0">if</FONT></B> t.name != name]
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">return</FONT></B> len(self.templates);

<B><FONT COLOR="#A020F0">class</FONT></B> Point:
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#BC8F8F">&quot;&quot;&quot;Simple representation of a point.&quot;&quot;&quot;</FONT></B>
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">def</FONT></B> <B><FONT COLOR="#0000FF">__init__</FONT></B>(self, x, y):
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.x = x
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.y = y

<B><FONT COLOR="#A020F0">class</FONT></B> Rectangle:
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#BC8F8F">&quot;&quot;&quot;Simple representation of a rectangle.&quot;&quot;&quot;</FONT></B>
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">def</FONT></B> <B><FONT COLOR="#0000FF">__init__</FONT></B>(self, x, y, width, height):
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.x = x
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.y = y
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.width = width
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.height = height

<B><FONT COLOR="#A020F0">class</FONT></B> Template:
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#BC8F8F">&quot;&quot;&quot;A gesture template. Used internally by Recognizer.&quot;&quot;&quot;</FONT></B>
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">def</FONT></B> <B><FONT COLOR="#0000FF">__init__</FONT></B>(self, name, points):
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#BC8F8F">&quot;&quot;&quot;'name' is a label identifying this gesture, and 'points' is a list of tuple co-ordinates representing the gesture positions. Example: [(1, 10), (3, 8) ...]&quot;&quot;&quot;</FONT></B>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.name = name
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.points = [Point(point[0], point[1]) <B><FONT COLOR="#A020F0">for</FONT></B> point <B><FONT COLOR="#A020F0">in</FONT></B> points]
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.points = _resample(self.points, numPoints);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.points = _rotateToZero(self.points);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.points = _scaleToSquare(self.points, squareSize);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.points = _translateToOrigin(self.points);


<B><FONT COLOR="#A020F0">def</FONT></B> <B><FONT COLOR="#0000FF">_resample</FONT></B>(points, n):
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#BC8F8F">&quot;&quot;&quot;Resample a set of points to a roughly equivalent, evenly-spaced set of points.&quot;&quot;&quot;</FONT></B>
&nbsp;&nbsp;&nbsp;I = _pathLength(points) / (n - 1) <I><FONT COLOR="#B22222"># interval length
</FONT></I>   D = 0.0
&nbsp;&nbsp;&nbsp;newpoints = [points[0]]
&nbsp;&nbsp;&nbsp;i = 1
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">while</FONT></B> i &lt; len(points) - 1:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;d = _distance(points[i - 1], points[i])
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">if</FONT></B> (D + d) &gt;= I:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;qx = points[i - 1].x + ((I - D) / d) * (points[i].x - points[i - 1].x)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;qy = points[i - 1].y + ((I - D) / d) * (points[i].y - points[i - 1].y)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;q = Point(qx, qy)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;newpoints.append(q)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<I><FONT COLOR="#B22222"># Insert 'q' at position i in points s.t. 'q' will be the next i
</FONT></I>         points.insert(i, q)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;D = 0.0
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">else</FONT></B>:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;D += d
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i += 1

&nbsp;&nbsp;&nbsp;<I><FONT COLOR="#B22222"># Sometimes we fall a rounding-error short of adding the last point, so add it if so.
</FONT></I>   <B><FONT COLOR="#A020F0">if</FONT></B> len(newpoints) == n - 1:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;newpoints.append(points[-1])
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">return</FONT></B> newpoints;

<B><FONT COLOR="#A020F0">def</FONT></B> <B><FONT COLOR="#0000FF">_rotateToZero</FONT></B>(points):
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#BC8F8F">&quot;&quot;&quot;Rotate a set of points such that the angle between the first point and the centre point is 0.&quot;&quot;&quot;</FONT></B>
&nbsp;&nbsp;&nbsp;c = _centroid(points)
&nbsp;&nbsp;&nbsp;theta = math.atan2(c.y - points[0].y, c.x - points[0].x)
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">return</FONT></B> _rotateBy(points, -theta)

<B><FONT COLOR="#A020F0">def</FONT></B> <B><FONT COLOR="#0000FF">_rotateBy</FONT></B>(points, theta):
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#BC8F8F">&quot;&quot;&quot;Rotate a set of points by a given angle.&quot;&quot;&quot;</FONT></B>
&nbsp;&nbsp;&nbsp;c = _centroid(points);
&nbsp;&nbsp;&nbsp;cos = math.cos(theta);
&nbsp;&nbsp;&nbsp;sin = math.sin(theta);
&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;newpoints = [];
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">for</FONT></B> point <B><FONT COLOR="#A020F0">in</FONT></B> points:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;qx = (point.x - c.x) * cos - (point.y - c.y) * sin + c.x
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;qy = (point.x - c.x) * sin + (point.y - c.y) * cos + c.y
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;newpoints.append(Point(qx, qy))
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">return</FONT></B> newpoints

<B><FONT COLOR="#A020F0">def</FONT></B> <B><FONT COLOR="#0000FF">_scaleToSquare</FONT></B>(points, size):
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#BC8F8F">&quot;&quot;&quot;Scale a scale of points to fit a given bounding box.&quot;&quot;&quot;</FONT></B>
&nbsp;&nbsp;&nbsp;B = _boundingBox(points)
&nbsp;&nbsp;&nbsp;newpoints = []
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">for</FONT></B> point <B><FONT COLOR="#A020F0">in</FONT></B> points:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;qx = point.x * (size / B.width)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;qy = point.y * (size / B.height)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;newpoints.append(Point(qx, qy))
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">return</FONT></B> newpoints

<B><FONT COLOR="#A020F0">def</FONT></B> <B><FONT COLOR="#0000FF">_translateToOrigin</FONT></B>(points):
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#BC8F8F">&quot;&quot;&quot;Translate a set of points, placing the centre point at the origin.&quot;&quot;&quot;</FONT></B>
&nbsp;&nbsp;&nbsp;c = _centroid(points)
&nbsp;&nbsp;&nbsp;newpoints = []
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">for</FONT></B> point <B><FONT COLOR="#A020F0">in</FONT></B> points:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;qx = point.x - c.x
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;qy = point.y - c.y
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;newpoints.append(Point(qx, qy))
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">return</FONT></B> newpoints;

<B><FONT COLOR="#A020F0">def</FONT></B> <B><FONT COLOR="#0000FF">_distanceAtBestAngle</FONT></B>(points, T, a, b, threshold):
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#BC8F8F">&quot;&quot;&quot;Search for the best match between a set of points and a template, using a set of tolerances. Returns a float representing this minimum distance.&quot;&quot;&quot;</FONT></B>
&nbsp;&nbsp;&nbsp;x1 = phi * a + (1.0 - phi) * b
&nbsp;&nbsp;&nbsp;f1 = _distanceAtAngle(points, T, x1)
&nbsp;&nbsp;&nbsp;x2 = (1.0 - phi) * a + phi * b
&nbsp;&nbsp;&nbsp;f2 = _distanceAtAngle(points, T, x2)

&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">while</FONT></B> abs(b - a) &gt; threshold:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">if</FONT></B> f1 &lt; f2:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b = x2
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x2 = x1
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;f2 = f1
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x1 = phi * a + (1.0 - phi) * b
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;f1 = _distanceAtAngle(points, T, x1)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">else</FONT></B>:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a = x1
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x1 = x2
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;f1 = f2
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x2 = (1.0 - phi) * a + phi * b
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;f2 = _distanceAtAngle(points, T, x2)
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">return</FONT></B> min(f1, f2)

<B><FONT COLOR="#A020F0">def</FONT></B> <B><FONT COLOR="#0000FF">_distanceAtAngle</FONT></B>(points, T, theta):
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#BC8F8F">&quot;&quot;&quot;Returns the distance by which a set of points differs from a template when rotated by theta.&quot;&quot;&quot;</FONT></B>
&nbsp;&nbsp;&nbsp;newpoints = _rotateBy(points, theta)
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">return</FONT></B> _pathDistance(newpoints, T.points)

<B><FONT COLOR="#A020F0">def</FONT></B> <B><FONT COLOR="#0000FF">_centroid</FONT></B>(points):
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#BC8F8F">&quot;&quot;&quot;Returns the centre of a given set of points.&quot;&quot;&quot;</FONT></B>
&nbsp;&nbsp;&nbsp;x = 0.0
&nbsp;&nbsp;&nbsp;y = 0.0
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">for</FONT></B> point <B><FONT COLOR="#A020F0">in</FONT></B> points:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x += point.x
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;y += point.y
&nbsp;&nbsp;&nbsp;x /= len(points)
&nbsp;&nbsp;&nbsp;y /= len(points)
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">return</FONT></B> Point(x, y)

<B><FONT COLOR="#A020F0">def</FONT></B> <B><FONT COLOR="#0000FF">_boundingBox</FONT></B>(points):
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#BC8F8F">&quot;&quot;&quot;Returns a Rectangle representing the bounding box that contains the given set of points.&quot;&quot;&quot;</FONT></B>
&nbsp;&nbsp;&nbsp;minX = float(<B><FONT COLOR="#BC8F8F">&quot;+Infinity&quot;</FONT></B>)
&nbsp;&nbsp;&nbsp;maxX = float(<B><FONT COLOR="#BC8F8F">&quot;-Infinity&quot;</FONT></B>)
&nbsp;&nbsp;&nbsp;minY = float(<B><FONT COLOR="#BC8F8F">&quot;+Infinity&quot;</FONT></B>)
&nbsp;&nbsp;&nbsp;maxY = float(<B><FONT COLOR="#BC8F8F">&quot;-Infinity&quot;</FONT></B>)

&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">for</FONT></B> point <B><FONT COLOR="#A020F0">in</FONT></B> points:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">if</FONT></B> point.x &lt; minX:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;minX = point.x
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">if</FONT></B> point.x &gt; maxX:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;maxX = point.x
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">if</FONT></B> point.y &lt; minY:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;minY = point.y
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">if</FONT></B> point.y &gt; maxY:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;maxY = point.y

&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">return</FONT></B> Rectangle(minX, minY, maxX - minX, maxY - minY)

<B><FONT COLOR="#A020F0">def</FONT></B> <B><FONT COLOR="#0000FF">_pathDistance</FONT></B>(pts1, pts2):
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#BC8F8F">&quot;&quot;&quot;'Distance' between two paths.&quot;&quot;&quot;</FONT></B>
&nbsp;&nbsp;&nbsp;d = 0.0;
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">for</FONT></B> index <B><FONT COLOR="#A020F0">in</FONT></B> range(len(pts1)): <I><FONT COLOR="#B22222"># assumes pts1.length == pts2.length
</FONT></I>      d += _distance(pts1[index], pts2[index])
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">return</FONT></B> d / len(pts1)

<B><FONT COLOR="#A020F0">def</FONT></B> <B><FONT COLOR="#0000FF">_pathLength</FONT></B>(points):
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#BC8F8F">&quot;&quot;&quot;Sum of distance between each point, or, length of the path represented by a set of points.&quot;&quot;&quot;</FONT></B>
&nbsp;&nbsp;&nbsp;d = 0.0;
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">for</FONT></B> index <B><FONT COLOR="#A020F0">in</FONT></B> range(1, len(points)):
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;d += _distance(points[index - 1], points[index])
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">return</FONT></B> d

<B><FONT COLOR="#A020F0">def</FONT></B> <B><FONT COLOR="#0000FF">_distance</FONT></B>(p1, p2):
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#BC8F8F">&quot;&quot;&quot;Distance between two points.&quot;&quot;&quot;</FONT></B>
&nbsp;&nbsp;&nbsp;dx = p2.x - p1.x
&nbsp;&nbsp;&nbsp;dy = p2.y - p1.y
&nbsp;&nbsp;&nbsp;<B><FONT COLOR="#A020F0">return</FONT></B> math.sqrt(dx * dx + dy * dy)

</PRE>
</td></tr></table>
<hr>

      <p><center><font size="-1"><i><b>Powered by <a href="http://websvn.tigris.org/">WebSVN</a> v1.61</b></i></font></center>
   </body>
</html>
